#include <iostream>
#include <vector>
#include <ctime>
#include <iomanip>
#include "BalanceTree.h"

#define UPBOUND 65535   /// = 16个1

using namespace std;

template <typename T>
void Avl_sort(std::vector<T> &_data)
{  
    AvlTree<T> tr;
    for (int i = 0; i < _data.size(); i++)
        tr.insert(_data[i]);

    _data.clear();
    while (!tr.isEmpty())
    {
        T x = tr.findMin();
        tr.remove(x);
        _data.push_back(x);
    }
}

template <typename T>
void Randomized_Avl_sort(std::vector<T> &_data)
{
    random_shuffle(_data.begin(),_data.end());
    Avl_sort(_data);
}

template <typename T>
void Splay_sort(std::vector<T> &_data)
{  
    SplayTree<T> tr;
    for (int i = 0; i < _data.size(); i++)
        tr.insert(_data[i]);

    _data.clear();
    while (!tr.isEmpty())
    {
        T x = tr.findMin();
        tr.remove(x);
        _data.push_back(x);
    }
}

template <typename T>
void Randomized_Splay_sort(std::vector<T> &_data)
{
    random_shuffle(_data.begin(),_data.end());
    Splay_sort(_data);
}

int main()
{
    clock_t start,end;
    srand((unsigned)time(NULL));

    std::cout << "Test 1 : 100 ramdom numbers.Use Randomized sort." <<std::endl;
    vector<int> a,b;
    for(int i = 0; i < 100; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }
/*    
    ///输出这一串未排列的数据
    cout << "There are some random numbers!" << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;
*/
    ///对这串数据进行排序
    start = clock();
    Randomized_Avl_sort(a);
    end = clock();
/*
    ///输出排好序的a
    cout << "Here is the ordered sequence!" << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;
*/
    double endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "AvlTree   : " << endtime*1000 << "ms" <<endl;

    start = clock();
    Randomized_Splay_sort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "SplayTree : " << endtime*1000 << "ms" <<endl;

    //
    std::cout << "Test 2 : 10000 ramdom numbers.Use Randomized sort." <<std::endl;
    a.clear();
    b.clear();
    for(int i = 0; i < 10000; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }

    start = clock();
    Randomized_Avl_sort(a);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "AvlTree   : " << setw(7) << endtime*1000 << "ms" <<endl;

    start = clock();
    Randomized_Splay_sort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "SplayTree : " << setw(7) << endtime*1000 << "ms" <<endl;

    std::cout << "Test 3 : 1000000 ramdom numbers.Use Randomized sort." <<std::endl;
    a.clear();
    b.clear();
    for(int i = 0; i < 1000000; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }

    start = clock();
    Randomized_Avl_sort(a);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "AvlTree   : " << setw(7) << endtime*1000 << "ms" <<endl;

    start = clock();
    Randomized_Splay_sort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "SplayTree : " << setw(7) << endtime*1000 << "ms" <<endl;

    return 0;
}